package leetcode;

import structure.tree.BinaryTree;

import java.lang.instrument.Instrumentation;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 145. 二叉树的后序遍历
 * 给定一个二叉树，返回它的 后序 遍历。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,null,2,3]
 * 1
 * \
 * 2
 * /
 * 3
 * <p>
 * 输出: [3,2,1]
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 */
public class PostOrderTraversal {

    // 使用递归
    List<Integer> result = new LinkedList<>();
    public List<Integer> postorderTraversal0(TreeNode root) {
        while (root != null) {
            postorderTraversal0(root.left);
            postorderTraversal0(root.right);
            result.add(root.val);
        }
        return result;
    }


    // 使用迭代 后序
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        LinkedList<Integer> result = new LinkedList<>();
        if (root == null){
            return result;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.addFirst(node.val);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }

        }
        return result;
    }

    // 使用迭代 中序遍历
    public List<Integer> minorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        List<Integer> result = new ArrayList<>();

        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {

            // 一道"撇"
            while (node != null) {
                stack.push(node.left);
                node = node.left;
            }
            // 根节点
            node = stack.pop();
            result.add(node.val);

            // 右节点
            node = node.right;
        }

        return result;
    }

}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;


    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

